When the Viterbi algorithm was proposed in 1967, it was presented as a method of decoding convolutional codes. Since that time, it has been recognized as an attractive solution to a variety of digital estimation problems. One of the first explanations of the Viterbi algorithm is provided in the article "The Viterbi Algorithm," from the Proceedings of the IEEE, Volume 61, pages 268-278, March, 1973.
The Viterbi algorithm can be explained by simple analogy as a method for finding the shortest path between two points (or more generally "states"). Consider the exemplary "map" shown in FIG. 1. A plurality of points are variably spaced from each other. Individual numbers are associated with each line referred to as a branch connecting two points with that number representing distance between the two points. Many possible routes referred to as "paths" connecting various different intermediate points exist between point A and point B (and in fact the Viterbi algorithm used in practice often considers millions or trillions of possible paths).
The Viterbi algorithm starts from point A and assigns an initial accumulated "metric" of zero to node A and initially sets a time index n to zero. Metric corresponds in this example to distance but also represents more generally a weight or probability associated with a particular path. The Viterbi algorithm then
1. Determines all possible states (called successors) at time instance n+1 which are a one "branch" extension (a branch being a single segment connection between two states) from a "predecessor state" being considered at time n. In this example, point A at time n=0 is the predecessor state for states A.sub.1, A.sub.2. A.sub.3 and A.sub.4 at time n=1. PA1 2. For each successor state, all paths (a path being a particular series of branches connecting a set of states) that lead or merge into that successor state are examined. In addition, a metric is calculated for each of those paths merging into that successor state. Each path metric equals the sum of an already accumulated path metric assigned to the predecessor state and the "branch metric" corresponding to the branch leading from the predecessor state to the successor state at time n. This step is often referred to as the "Add" step of the Viterbi algorithm. PA1 3. Less "competitive" paths are eliminated with competitiveness being measured in terms of accumulated path metrics. Each path's metric is compared with the other competing path metrics until only the shortest path (called the "survivor") remains along with that successor's accumulated metric. This process includes two steps often referred as the "Compare" and "Select" steps of the Viterbi algorithm. PA1 4. Steps 2 and 3, i.e., the Add, Compare, and Select steps, are repeated for all successor states. PA1 5. Steps 1-4 are repeated for all states at time n and then the processor continues to the next time interval n+1.
Generally, if there is only one branch leading into a state, it is the survivor. If there is a tie when comparing path matrics, one of the paths is randomly selected.
Once a survivor path is chosen and the Viterbi algorithm is complete, the received information is estimated, i.e. decoded. Each state (or branch) along the chosen survivor corresponds to a particular symbol. Therefore, one symbol corresponding to the selected state is decoded for each time interval.
In essence, the Viterbi algorithm is an efficient way of sorting all possible paths between the beginning point A and the ending point B and selecting the best path. A fundamental principle of the algorithm is that the most likely path to be selected (i.e. survive) must at any time begin with one of the survivor states. Although this example of the Viterbi algorithm is described in terms of distance between two points, the Viterbi algorithm is applicable to all problems which can be described as a finite state machine, i.e. the number of possible events is finite when the "machine" transitions from one state to the next.
With even a relatively small number of possible states at any one time interval, visualizing the number of possible branch decisions from one state to another state for successive time intervals is a difficult task. Therefore, trellis diagrams are often used to illustrate the finite state machine with the dimension of time added to show a different version of the state diagram for each time interval. In practical applications, a trellis diagram is configured based on characteristics of the physical system from which state transitions are being predicted. Each column in the trellis represents the number of possible states 1, 2, 3, 4 . . . with each state representing (in the digital data communications context) one or more symbols. There is one column for each time interval (or index) 0, 1, 2, . . . .
In radio communication applications, for example mobile radio communications including both cellular and land mobile radio, the Viterbi algorithm is often employed to decode digital data in the context of convolutional codes, adaptive equalization, and demodulation of intersymbol interference (ISI) corrupted signals. In these exemplary radio communication applications, the Viterbi algorithm estimates as a received signal sequence R(n) the most likely transmitted signal sequence S(n) in the presence of quasi-predictable distortion sources on the communications channel C(n) and unpredictable noise sources N(n) corrupting the transmitted signal. The received signal therefore may be represented as follows: R(n)=S(n)C(n)+N(n). In this context, the Viterbi algorithm processes a block of received signal samples (which presumably have been modulated and/or coded in a transmitter), and chooses from the data received at a receiver a sequence of digital ones and zeroes that were most likely to have been transmitted.
The Viterbi algorithm is therefore generally characterized as a maximum likelihood sequence estimator (MLSE). Accordingly, the algorithm estimates/decides what sequence of ones and zeroes has been transmitted only after the entire logical sequence or block of received data being analyzed, e.g. a time slot of data in time division multiple access (TDMA) systems has been received and processed. Unfortunately, since a block of, for example, 160 symbols must be completely Viterbi analyzed before finalizing a decoded estimate of any one of the 160 symbols, there is a significant delay associated with this decision making process.
Such decision delay is undesirable in real time sequence estimation applications like mobile radio communications. For example, channel equalizers require intermediate updates of the channel characteristics C(n) in order to accurately estimate/predict those channel characteristics to reflect changes in the channel. On the other hand, the Viterbi algorithm is an MLSE, i.e., achieves the optimum performance, only when the decision depth is infinite. In practice, a decision depth of five to six times of the constraint length (memory) of the code may be used to achieve near-optimal sequence estimation.
But even such practical decision depths are unnecessarily long for certain sequence estimation applications. Consider an MLSE equalizer where a fixed decision depth D is chosen. At time n, the equalizer examines all survivors at time n-D (i.e. looking backward in time) and picks the survivor having the maximum metric. An intermediate decision resulting in one or more decoded bits corresponding to this maximum metric path at time n-D is sent back to a channel tracker. The channel tracker uses these decoded bits for time n-D to update the channel model estimate C(n) at time n. In other words, the channel tracker will not accurately predict the channel characteristic without some input regarding the sequence of symbols which have recently been decoded. Based on the signal block received and output by the updated channel tracker at time n, the Viterbi algorithm is then performed on all states at time n.
A problem arises that at time n, the Viterbi algorithm only produces a partial decode decision for decision time n-D. This decision at time n-D is then used to predict the channel at time n. If D is too large or the channel is varying quickly, i.e. a fast fading channel, the channel prediction becomes unreliable. Thus, there is trade off between accuracy of the ultimate sequence estimation (e.g., as measured by bit error rate (BER)) and the accuracy and stability of tracking the characteristics of a particular communications channel which in turn also affects BER. The choice of an appropriate decision depth D for various rates of fading is a compromise balance of bit error rate and the effectiveness of the channel tracking algorithm.
In a typical communications channel, (e.g. one based on a white Gaussian noise model), the difference in the metric associated between the selected path (the maximum metric) and other paths rises exponentially with time. In fact, for favorable communications conditions, the MSLE path selection process can operate effectively using a decision depth that is less that the fixed decision depth D. In contrast, fading communication channels may require longer time/decision depth to distinguish the maximum metric path from the other paths. A variable decision depth would provide a way to efficiently adapt to favorable and unfavorable channel conditions.
Accordingly, the present invention provides a variable decision depth sequence estimator which can be dynamically adapted to the changing characteristics of the communications channel/application. When the channel condition is favorable, possible survivor trellis paths associated with a current trellis stage being decoded typically converge before a maximum decision delay expires. With a maximum decision depth preset, early path convergence to a single survivor state is detected to provide current decoded symbols for updating the most recent channel predictions. When the survivor paths converge quickly, the present invention reduces the decision delay from the fixed delay. As a result, predicted channel estimation/tracking is improved because the prediction interval is shortened. Only when there are less favorable channel conditions, such as when shadowing or fading occur, would a unique survivor not exist at an earlier decision time. In that situation, a longer decision depth up to the maximum preset is employed. Therefore, the overall performance of an equalizer or the average delay of a decoder employing the technique of the present invention is improved over one using a fixed decision depth.
The decoder assigns group flags to each state for each time interval being considered and stores those group flags along with corresponding accumulated path metrics associated with each state. More specifically, from a just decoded state, flags from different groups, e.g. each group being represented by a color, a number, etc., are assigned to subsequent states connected by a survivor path to the just decoded state. Each offspring state of a parent state is assigned the parent's group flag. The decoder detects where in the trellis all of the survivor states have the same group flag. At this point where all the flags agree, the decoder back traces through the trellis to the parent state having that same group flag. That parent state is then decoded as the estimate of the symbol(s). Thereafter, group flags are reassigned and the procedure repeated using this newly decoded state as the new just decoded state.
These and other advantages and features of the present invention will become apparent from the following description of the preferred embodiments and from the claims.